class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size();
        int sum = 0;
        for (auto e : stones) sum += e;
        int s = sum / 2;
        vector<int> dp(s + 1);

        for (int i = 1; i <= n; ++i)
            for (int j = s; j >= stones[i - 1]; --j)
                dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);

        return sum - 2 * dp[s];
    }
};